Key to CSE142 Final, Winter 2014        

1.      Original Array            Final Array
        ---------------------------------------
        {4, 7}                    {4, 3}
        {3, 16, 5, 10};           {3, 8, 5, 5}
        {5, 6, 5, 4};             {5, 3, 2, 2}
        {3, 8, 13, 6, 12};        {3, 4, 6, 6, 6}

2. Reference Mystery.  The program produces the following output:
        2 -5 [2, 4, -5, 8]
        1 -4 [2, 4, -5, 8]
        3 -5 [2, 4, -4, -5]
        2 -4 [2, 4, -4, -5]

3. Inheritance Mystery.  The program produces the following output:

        rust
        red 1 red 2 rust 1
        red 2 

        rust
        red 1 ruby 2 rust 1
        ruby 2 

        red
        red 1 red 2 
        red 2 

        red
        lava 1 
        red 2

4. Token-based processing.  One possible solution:

public static int censorNames(Scanner fileScan) {
  int names = 0;
  
  while (fileScan.hasNext()) {
     names++;
     
     System.out.print(fileScan.next() + " ");
     String lname = fileScan.next();
     for (int i = 0; i < lname.length(); i++) {
        System.out.print("X");
     }
     System.out.println();
  }
  return names;
}

5. Line-based processing.  One possible solution:

public static void hoursWorked(Scanner fileScan, String name) {
   double totalHours = 0;
   int days = 0;
         
   while (fileScan.hasNextLine()) {
      String line = fileScan.nextLine();
      
      Scanner lineScan = new Scanner(line);
      boolean inLine = false;
      String heading = lineScan.next();
      while (lineScan.hasNext()) {
         if (lineScan.next().equals(name)) {
            inLine = true;
            totalHours += 0.5;
         }
      }
      
      if (inLine) {
         days++;
      }
   } 
   
   if (totalHours > 0) {
      System.out.println(name + " worked " + totalHours + " hours over " + days + " days.");
   } else {
      System.out.println(name + " not found.");
   }
}

6. Array programming.  Three possible solutions:

public static boolean isAllPairs(int[] arr) {
   if (arr.length % 2 == 1) {
      return false;
   }
   for (int i = 1; i < arr.length; i += 2) {
      if (arr[i] != arr[i - 1]) {
         return false;
      }
   }
   return true;
}

public static boolean isAllPairs(int[] arr) {
   if (arr.length % 2 != 0) {
      return false;
   }
   for (int i = 0; i < arr.length / 2; i++) {
      if (arr[2 * i] != arr[2 * i + 1]) {
         return false;
      }
   }
   return true;
}

public static boolean isAllPairs(int[] arr) {
   if (arr.length % 2 == 1) {
      return false;
   }
   int pairs = 0;
   for (int i = 1; i < arr.length; i += 2) {
      if (arr[i] == arr[i - 1]) {
         pairs++;
      }
   }
   
   return pairs == arr.length / 2;
}

7. Array programming.  Three possible solutions:
public static int[] insertMiddle(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    for (int i = 0; i < a.length / 2; i++) {
        result[i] = a[i];
    }
    
    for (int i = 0; i < b.length; i++) {
        result[i + a.length / 2] = b[i];
    }
    
    for (int i = a.length / 2; i < a.length; i++) {
        result [i + b.length] = a[i];
    }

    return result;
}

public static int[] insertMiddle(int[] a, int[] b) {
    int lengthA = a.length;
    int lengthB = b.length;
    int[] result = new int[lengthA + lengthB];
    for (int i = 0; i < result.length; i++) {
        if (i < lengthA / 2)
            result[i] = a[i];
        else if (i < (lengthA / 2 + lengthB))
            result[i] = b[i - lengthA / 2];
        else
            result[i] = a[i - lengthB];
    }
    return result;
}

public static int[] insertMiddle(int[] a, int[] b) {
    int[] c = new int[a.length + b.length];
    int n = 0;
    
    for (int i = 0; i < a.length / 2; i++) {
        c[n] = a[i];
        n++;
    }
    
    for (int i = 0; i < b.length; i++) {
        c[n] = b[i];
        n++;
    }
    
    for (int i = a.length / 2; i < a.length; i++) {
        c[n] = a[i];
        n++;
    }
    return c;
}

8. Critters.  One possible solution:

public class Wombat extends Critter {
   private int count;
   private String display;
   private Random r;
   
   public Wombat() {
      display = "?";
      r = new Random();
   }
   
   public Direction getMove() {
      count++;
      if (count % 3 == 0) {
         return Direction.NORTH;
      } else {
         return Direction.SOUTH;
      }
   }
   
   public Attack fight(String opponent) {
      display = opponent;
      if (opponent.equals("%")) {
         return Attack.ROAR;
      }
      return Attack.POUNCE;
   }
   
   public boolean eat() {
      int prob = r.nextInt(3);
      return prob < 1;
   }
   
   public String toString() {
      return display;
   }
}

9. Array programming.  Three possible solutions:

// starting from the back, shifting values as we go
public static void limitRuns(int[] nums, int n) {
    int count = 1;
    for (int i = nums.length - 1; i > 0; i--) {
        if (nums[i] == nums[i - 1]) {
            count++;
            if (count > n) {
                for (int j = i; j < nums.length - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                nums[nums.length - 1] = 0;
            }
        } else {
            count = 1;
        }
    }
}

// counting from front, shift over as we go
// need to be careful not to be stuck in infinite loop with 0s at end!
public static void limitRuns(int[] nums, int n) {
    int count = 1;
    int tot = 1;
    for (int i = 1; i < nums.length - tot + 1; i++) {
        if (nums[i] == nums[i - 1]) {
            count++;
            if (count > n) {
                for (int j = i; j < nums.length - tot; j++) {
                    nums[j] = nums[j + 1];
                }
                nums[nums.length - tot] = 0;
                tot++;
                i--;
            }
        } else {
            count = 1;
        }
    }
}

// keep count of the index of the last value to keep
public static void limitRuns(int[] nums, int n) {
    int nonReps = 1;
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1]) {
            count++;
        }
        
        if (nums[i] != nums[i - 1]) {
            count = 1;
        }
        
        if (nums[i] != nums[i - 1] || count <= n) {
            nums[nonReps] = nums[i];
            nonReps++;
        } 
    }
    
    for (int i = nonReps; i < nums.length; i++) {
        nums[i] = 0;
    }
}